from 超级水王 import hashmap as hh
import time
'''
遍历序列，当有两个不同元素时，消去这两个元素
当水王元素存在时，最终列表中剩余元素一定为水王元素

代码思想：
设置待定位以及血量
当血量为0时，像待定位中添加遍历到的元素
当血量不为0也就是待定位中含有元素时
判断遍历到的元素与待定位中元素是否相等
若相等血量减一
若不相等血量加一
遍历完毕之后，若血量为0，待定位中不含有元素，没有水王
若血量不为0，对序列遍历统计待定位中元素出现次数，若次数大于序列长度元素的一般，
返回该元素，否则不存在水王
'''
def solveWater(waterList):
    candidate = 0
    restHP = 0
    for water in waterList:
        if restHP == 0:
            candidate = water
            restHP += 1
        elif water != candidate:
            restHP -= 1
        else:
            restHP += 1
    if restHP == 0:
        return -1
    count = 0
    for water in waterList:
        if water == candidate:
            count += 1
    #print("候选：{},出现次数:{}".format(candidate,count))
    return candidate if count > len(waterList) / 2 else  -1
if __name__ == '__main__':
    waterList = hh.creatList()
    startTime = time.time()
    frequency = 10000
    for i in range(frequency):
        hh.solveWater(waterList)
    endTime = time.time()
    print("哈希表解决水王问题{}次，所用时间为：{}s".format(frequency,endTime-startTime))
    startTime = time.time()
    for i in range(frequency):
        solveWater(waterList)
    endTime = time.time()
    print("消去两个不同元素解决水王问题{}次，所用时间为：{}s".format(frequency,endTime-startTime))
    '''
    哈希表解决水王问题10000次，所用时间为：15.177638530731201s
    消去两个不同元素解决水王问题10000次，所用时间为：1.221430778503418s
    
    时间效率相差十多倍！！！！！！！！！！！！！！
    NB！！！！
    '''